#include "shellsort.h"

ShellSort::ShellSort(QObject *parent):
    IAlgo(parent)
{

}

QString ShellSort::name()
{
    return "Shell Sort";
}

void ShellSort::run()
{
    _run_time = 0;
    QVector<int> &data = _data->GetData();

    for(int i = data.size()/2; i >= 1; i /= 2){
        sortGroup(i);
    }
}

void ShellSort::sortGroup(int gap)
{
    QVector<int> &data = _data->GetData();
    for(int i = gap; i < data.size(); i += gap){
        int item = data[i];
        int j = i - gap;
        while(j >= 0 && data[j] > item){
            data[j + gap] = data[j];
            j -= gap;
            ++_run_time;
            _data->Refresh();
        }
        data[j + gap] = item;
        ++_run_time;
        _data->Refresh();
    }
}
